package algorithm;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * @author rongkai
 * @description:
 * @date 2021/3/8
 */
public class Solution16 {

    public static void main(String[] args) {
        int[] nums = {-2,-3,4,-1,2,1,-5,4};
        System.out.println(solution(nums));
    }


    /**
     * 解题思路: 每一个子数组的最大值都等于上一个子数组的值加上当前的值，两值相比较娶其大
     * @param nums
     * @return
     */
    public static int solution(int[] nums){
        int max = nums[0], maxEndingHere = nums[0];
        for (int i = 1; i < nums.length; ++i)
        {
            maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);
            max = Math.max(max, maxEndingHere);  // update max
        }
        return max;
    }
}
